11352 - Crazy king/11352.cpp

   1 #include <iostream>
   2 #include <climits>
   3 #include <queue>
   4
   5 using namespace std;
   6
   7 char g[101][101];
   8
   9 int deltaCol[] = {-2, -1,  1,  2, 2, 1, -1, -2};
  10 int deltaFil[] = {-1, -2, -2, -1, 1, 2,  2,  1};
  11
  12 int rdeltaCol[] = { -1,  0,  1, 1, 1, 0, -1, -1};
  13 int rdeltaFil[] = { -1, -1, -1, 0, 1, 1,  1,  0};
  14
  15 int inicialCol, inicialFil;
  16
  17 char color[101][101];
  18 unsigned int d[101][101];
  19
  20 int m, n; //m filas, n columnas
  21
  22 const int WHITE = 0;
  23 const int GRAY = 1;
  24 const int BLACK = 2;
  25
  26 void bfs(){
  27   memset(color, WHITE, sizeof(color));
  28   //memset(d, 2147483647, sizeof(d));
  29
  30   for (int i=0; i<=100; ++i) for (int j=0; j<=100; ++j) d[i][j] = UINT_MAX;
  31
  32   color[inicialFil][inicialCol] = GRAY;
  33   d[inicialFil][inicialCol] = 0;
  34
  35   queue< pair<int,int> > q;
  36   q.push(make_pair(inicialFil, inicialCol));
  37
  38   //printf("Empezando en: (%d,%d)\n", inicialFil, inicialCol);
  39
  40   while (!q.empty()){
  41     int fil = q.front().first, col = q.front().second;
  42
  43     //printf("Saque el nodo (%d,%d) de la cola.\n", fil, col);
  44
  45     if (g[fil][col] == 'B'){
  46       cout << "Minimal possible length of a trip is ";
  47       cout << d[fil][col] << endl;
  48       return;
  49     }
  50
  51     for (int k=0; k<8; ++k){
  52       int tempFil, tempCol;
  53       tempFil = fil + rdeltaFil[k];
  54       tempCol = col + rdeltaCol[k];
  55       //if (tempFil >= 0 && tempFil < m && tempCol >= 0 && tempCol < n){
  56       if ( (tempFil >= 0) && (tempFil < m) && (tempCol >= 0) && (tempCol < n)){
  57         char c = g[tempFil][tempCol];
  58
  59         //printf("Considerando para marcado el nodo(%d,%d) que contiene %c\n", tempFil, tempCol, c);
  60
  61         if (c != 'Z' && c != 'X'){
  62
  63           //printf("Nodo visitable (%d,%d), revisando que sea blanco.\n", tempFil, tempCol);
  64
  65           if (color[tempFil][tempCol] == WHITE){
  66             color[tempFil][tempCol] = GRAY;
  67
  68             //printf("Marcando gris el nodo (%d,%d)\n", tempFil, tempCol);
  69
  70             d[tempFil][tempCol] = d[fil][col] + 1;
  71             q.push(make_pair(tempFil, tempCol));
  72           }
  73         }
  74       }
  75     }
  76     q.pop();
  77     color[fil][col] = BLACK;
  78   }
  79   printf("King Peter, you can't go now!\n");
  80 }
  81
  82
  83 int main(){
  84   int casos;
  85   cin >> casos;
  86   while (casos--){
  87     cin >> m >> n;
  88     for (int i=0; i<m; ++i){
  89       for (int j=0; j<n; ++j){
  90         char c;
  91         cin >> c;
  92         g[i][j] = c;
  93         if (c == 'A'){
  94           inicialFil = i;
  95           inicialCol = j;
  96         }
  97       }
  98     }
  99
 100
 101
 102     for (int i=0; i<m; ++i){
 103       for (int j=0; j<n; ++j){
 104         if (g[i][j] == 'Z'){
 105           for (int k=0; k<8; ++k){
 106             int tempFil, tempCol;
 107             tempFil = i + deltaFil[k];
 108             tempCol = j + deltaCol[k];
 109             if (tempFil >= 0 && tempFil <= m && tempCol >=0 && tempCol < n){
 110               char c = g[tempFil][tempCol];
 111               if (c != 'B' && c != 'A' && c != 'Z') g[tempFil][tempCol] = 'X';
 112             }
 113           }
 114         }
 115       }
 116     }
 117
 118     //En este momento, g[i][j] contiene una X si es una casilla atacable
 119
 120     bfs();
 121
 122
 123     /*for (int i=0; i<m; ++i){
 124       for (int j=0; j<n; ++j){
 125         cerr << g[i][j];
 126       }
 127       cerr << endl;
 128     }
 129     cerr << endl;
 130     */
 131
 132
 133   }
 134 }